The last few years have seen a significant growth in of Synchronous Optical NETwork (SONET) and Synchronous Digital Hierarchy (SDH) deployments by telecommunications service providers. (Since the present invention applies to SONET, SDH and similar network protocols equally well, only SONET networks will be explicitly discussed hereinafter.)
While initially intended for voice traffic, SONET networks have come to provide the underlying transport for the growing Internet data traffic. Unfortunately, unlike voice, data traffic has more variance and therefore creates greater “churn” (a building up and tearing down of links) in the network. As the data traffic continues to grow and the capital budgets of service providers fail to keep up (or even diminish), providers are increasingly seeking network engineering tools that enable them to extract higher utilization from their existing infrastructure.
Referring initially to FIGS. 1A and 1B, illustrated is a graphical, schematic representation of an exemplary network engineering operation. The operation involves an 8-node STS-12 Bidirectional Line-Switched Ring (BLSR) (see, e.g., Goralski, SONET, 2nd ed., McGraw-Hill Companies, 2000, incorporated herein by reference in its entirety) represented as a 12×8 grid, split across node 1 with the x-axis representing the nodes and the y-axis the time slots.
FIG. 1A shows as shaded rectangles five circuits (circuits A, B, C, D, E) on the ring. For example, a STS-1 circuit A exists from node 3 to 6 on slot 1, and a STS-3c circuit B exists on slots 1-3 from node 2 to 7. A circuit can be routed in either clockwise or counter-clockwise direction (as in the case of circuit B). Now, for purposes of the demonstration, a new request is made for a STS-12c circuit from node 2 to 7. Unfortunately, the request would be denied, because 12 contiguous slots of bandwidth between nodes 2 and 7 do not exist. Unfortunately, sufficient bandwidth does in fact exist on the ring for the STS-12c demand, but, as FIG. 1A makes apparent, it is fragmented.
Turning now to FIG. 1B, the same five circuits A, B, C, D, E have now been routed differently. In this layout, the new STS-12c circuit request would be granted. The new layout is the product of effective network engineering.
As beneficial as it has been demonstrated to be, network engineering suffers a critical constraint. Since it is performed on operational networks that carry live traffic, it should be hitless, i.e., cause no service disruption. Thus, in addition to optimizing the layout of circuits, it is equally important to determine a hitless rerouting sequence to migrate the ring from the original to this new layout. Otherwise, rerouting is of little practical use.
In traditional SONET rings consisting of add-drop elements, rerouting traffic was often a cumbersome task and in many cases, impossible to achieve without disruption. However, newer SONET network elements are increasingly supporting traditional add-drop capability with a more mesh-like cross-connect functionality. Thus, these new element can support a “bridge-and-roll” functionality (see, M.3100, “Definition of the Management Interface for a Bridge-and-Roll Cross-Connect Feature,” Amendment 4, ITU-T, August 2001, incorporated herein by reference in its entirety). This enables circuits to be first bridged on to the new route and then rolled over seamlessly with no service interruption, akin to make-before-break in MPLS (see, e.g., Awduche, et al., “RSVP-TE: Extension to RSVP for LSP Tunnels,” IETF RFC 3209, 2001, incorporated herein by reference in its entirety).
Three ways exist to reroute circuits on a SONET ring: (1) moving a circuit to a different time slot (e.g., circuit C), (2) reversing the direction of the route of the circuit (e.g., from a clockwise to a counter-clockwise direction (e.g., circuit D) and (3) doing both (e.g., circuit B). Thus, rerouting circuits C, D and B (in that order) using bridge-and-roll ensures a migration with no perceived service hit.
The requirement to provide a disruption-free transition sequence fundamentally differentiates network engineering from network design. Moreover, it precludes periodically redesigning the circuit routes to achieve the same goal. Network engineering, thus, requires addressing two critical, yet distinct problems: “route design” and “path migration,” both of which are theoretically “hard” problems to solve. Scaling network engineering to larger rings (e.g., STS-48/192) with more nodes proves an extremely difficult challenge.
Extensive research has been done in the area of SONET ring design. For example, Cosares, et al., “An Optimization Problem Related to Balancing Loads on SONET Rings,” Telecommunication Systems, vol. 3, 1994, incorporated herein by reference in its entirety; Myung, et al., “Optimal Load Balancing On SONET Bidirectional Rings,” Operations Research, vol. 45, January 1997 incorporated herein by reference in its entirety; and Schrijver, et al., “The Ring Loading Problem,” SIAM Journal of Discrete Math, vol. 11, no. 1, February 1998, incorporated herein by reference in its entirety, have studied the SONET ring loading portion of the problem and developed efficient heuristic algorithms. The portion of the problem that involves assigning time slots given a routing, is known to be NP-hard (see, e.g., Garey, et al., Computers and Intractability—A Guide to the Theory of NP-Completeness, Freeman, Calif., USA, 1979, incorporated herein by reference in its entirety) and follows from the circular arc graph coloring problem. A comprehensive treatment of all the aspects of SONET ring design is available in Carpenter, et al., “Demand Routing and Slotting on Ring Networks,” DIMACS technical Report, Tech. Rep., January 1997 incorporated herein by reference in its entirety; and Cosares, et al., “Network Planning with SONET Toolkit,” Bellcore Exchange, September 1992, incorporated herein by reference in its entirety.
Unfortunately, these contributions do not account for the alignment property, which will be described in detail below. Unlike ring design, very little prior work has been undertaken on the hitless path migration problem. Shepherd, et al. (“Hardness of Path Exchange Problem,” Personal Communication, incorporated herein by reference in its entirety) proved that path migration is NP-hard in the general case of a mesh network.
Accordingly, what is needed in the art are effective systems and methods for achieving hitless network engineering with respect to SONET (and similar) rings.